As an encoding method for reversibly compressing a fixed-length integer string, a method is used where a predicted value for data to be encoded is first determined, a residual between the predicted value and the data to be encoded is then determined, and a data series constituted from the residual is encoded using an appropriate method. That is, this method is constituted from predicted value generation of determining the predicted value for the data to be encoded, residual generation of determining the residual between the predicted value and the data to be encoded, and residual encoding of encoding the data series constituted from the residual using the appropriate method.
In this method, the data series constituted from a smaller value than an actual data series or a value near 0 is obtained by 0 interposing a stage of determining the residual. Thus, according to this method, the residual encoding with respect to the data to be encoded often easily becomes effective to enhance a compression effect.
There is provided a method of adopting a difference from a last value as the residual, as an example of the predicted value generation and the residual generation. Specifically, the last value is selected as the predicted value, and a simple subtracted value of an integer value is adopted as the residual, as a residual generation method. More generally, a method of linear prediction or the like is selected for the predicted value.
With respect to the residual encoding, various methods such as gamma encoding, delta encoding, and the like have been proposed. These methods of the residual encoding are broadly classified into two types of methods that are a method for compression ratio improvement and a method of improving a processing speed such as a compression speed, a decompression speed, or the like.
As the method for the compression ratio improvement, there is provided a method, as represented by Golomb-Rice coding, in which an integer value is divided into a first integer constituted from high-order bits and a second integer constituted from low-order bits at a defined position. Hereinafter, the encoding method of dividing an integer will be collectively referred to as a high- and low-order bits division method.
In the high- and low-order bits division method, the first integer constituted from the high-order bits is encoded by appropriate variable length encoding such as the gamma encoding or the delta encoding, and is then output. Then, the second integer constituted from the low-order bits is not encoded and is output as fixed-length binary data. In the Golomb-Rice coding, alpha coding is adopted as the encoding method of the first integer.
Patent Literature 1 discloses a method of enhancing a compression ratio by dynamically determining an encoding method of a first integer constituted from high-order bits and a dividing position of the high-order bits and low-order bits. Patent Literature 2 discloses an image compression method using the high- and low-order bits division method.
The high- and low-order bits division method is an effective method when a variation in the low-order bits is large because noise is mixed in an integer string to be compressed or the like. The basic concept of the high- and low-order bits division method is as follows. That is, since it is difficult to compress the low-order bits with the noise mixed therein, the low-order bits are output as the fixed-length binary data without being compressed. Then, only the high-order bits that are comparatively easy to compress are compressed.
When an integer string is bit-divided into high-order bits and low-order bits as illustrated in FIG. 8, the high-order bits become easy to compress and the low-order bits become difficult to compress.
As the method for improving the processing speed, there are a plurality of methods of performing encoding at a time of compression by increments of one byte or increments of one word which is further larger than the one byte. In the gamma encoding, the delta encoding, the Golomb-Rice encoding, or the like described before, a code is generated and output bit by bit. Thus, there is a problem that compatibility with computer processing is low, leading to reduction of a processing speed. A method that has been proposed in order to solve such a problem is a method of generating a code byte by byte or word by word and outputting the code. Herein, a word is a unit of a fixed length, and indicates the unit of 2 bytes or 4 bytes, for example. Hereinafter, the compression methods of generating the code byte by byte and word by word will be respectively referred to as a byte-based processing method and a word-based processing method.
As an example of the byte-based processing method, an encoding method such as Variable-Byte (Non-Patent Literature 1) is well known. As the word-based processing method, Simple9 (Non-Patent Literature 2), PForDelta (Non-Patent Literature 3), and so on are well known. In the gamma encoding, the delta encoding, the Golomb-Rice coding, and so on, integers are encoded one by one. In the word-based encoding method, a plurality of integers are collectively encoded, and a result of the encoding is generated word by word.